Richard Karp

Richard Manning Karp

Richard Karp giving a talk at the EPFL on 13th of July 2009
Born January 3, 1935 (1935-01-03)
Boston, Massachusetts
Nationality American
Fields Computer Science
Institutions IBM
University of California, Berkeley
University of Washington
Doctoral advisor Anthony Oettinger[1]
Doctoral students Narendra Karmarkar
Michael Luby
Rajeev Motwani
Barbara Simons
Known for Edmonds–Karp algorithm
Karp's 21 NP-complete problems
Hopcroft–Karp algorithm
Karp–Lipton theorem
Rabin–Karp string search algorithm
Notable awards Turing Award
National Medal of Science
Benjamin Franklin Medal
Kyoto Prize

Richard Manning Karp (born 1935) is a computer scientist and computational theorist, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.[2]

Contents

Biography

Born to Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. He attended Harvard University, where he received his Bachelor's degree in 1955, his Master's degree in 1956, and his Ph.D. in applied mathematics in 1959.

He started working at IBM's Thomas J. Watson Research Center. In 1968, he became Professor of Computer Science, Mathematics, and Operations Research at the University of California, Berkeley. Apart from a 4-year period as a professor at the University of Washington, he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a Research Scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group.

Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He is the recipient of several honorary degrees.

Work

He has made many other important discoveries in computer science and operations research in the area of combinatorial algorithms. His major current research interests include bioinformatics.

In 1971 he co-developed with Jack Edmonds the Edmonds–Karp algorithm for solving the max-flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 Problems to be NP-complete[3].

In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, still the fastest known method for finding maximum cardinality matchings in bipartite graphs.

In 1980, along with Richard J. Lipton, Karp proved the Karp-Lipton theorem (which proves that, if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level).

In 1987 he co-developed with Michael O. Rabin the Rabin-Karp string search algorithm.

Turing Award

His citation[4] for the Turing Award was as follows:

For his continuing contributions to the theory of algorithms including the development of efficient algorithms for network flow and other combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably, contributions to the theory of NP-completeness. Karp introduced the now standard methodology for proving problems to be NP-complete which has led to the identification of many theoretical and practical problems as being computationally difficult.

References

  1. ↑ Richard Karp at the Mathematics Genealogy Project.
  2. ↑ http://www.inamori-f.or.jp/laureates/k24_a_richard/prs_e.html
  3. ↑ Richard M. Karp (1972). "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. 
  4. ↑ Association for Computing Machinery. "ACM Award Citation/Richard M. Karp". http://awards.acm.org/citation.cfm?id=3256708&srt=all&aw=140&ao=AMTURING&yr=1985. Retrieved 2010-01-17. 

External links

Preceded by
John McCarthy		 Benjamin Franklin Medal in Computer and Cognitive Science
2004		 Succeeded by
Aravind Joshi
EATCS Award laureates

Karp (2000) · Böhm (2001) · Nivat (2002) · Rozenberg (2003) · Salomaa (2004) · Milner (2005) · Paterson (2006) · Scott (2007) · Valiant (2008) · Huet (2009) · Mehlhorn (2010)
A. M. Turing Award laureates

Alan Perlis (1966) · Maurice Vincent Wilkes (1967) · Richard Hamming (1968) · Marvin Minsky (1969) · James H. Wilkinson (1970) · John McCarthy (1971) · Edsger W. Dijkstra (1972) · Charles Bachman (1973) · Donald Knuth (1974) · Allen Newell / Herbert Simon (1975) · Michael O. Rabin / Dana Scott (1976) · John Backus (1977) · Robert Floyd (1978) · Kenneth E. Iverson (1979) · C. A. R. Hoare (1980) · Edgar F. Codd (1981) · Stephen Cook (1982) · Ken Thompson / Dennis Ritchie (1983) · Niklaus Wirth (1984) · Richard Karp (1985) · John Hopcroft / Robert Tarjan (1986) · John Cocke (1987) · Ivan Sutherland (1988) · William Kahan (1989) · Fernando J. Corbató (1990) · Robin Milner (1991) · Butler Lampson (1992) · Juris Hartmanis / Richard Stearns (1993) · Edward Feigenbaum / Raj Reddy (1994) · Manuel Blum (1995) · Amir Pnueli (1996) · Douglas Engelbart (1997) · Jim Gray (1998) · Fred Brooks (1999) · Andrew Yao (2000) · Ole-Johan Dahl / Kristen Nygaard (2001) · Ron Rivest / Adi Shamir / Leonard Adleman (2002) · Alan Kay (2003) · Vint Cerf / Bob Kahn (2004) · Peter Naur (2005) · Frances E. Allen (2006) · Edmund M. Clarke / E. Allen Emerson / Joseph Sifakis (2007) · Barbara Liskov (2008) · Charles P. Thacker (2009)
United States National Medal of Science laureates
 
Mathematical, statistical, and computer sciences
1960s

1963: Norbert Wiener · 1964: Solomon Lefschetz · H. Marston Morse · 1965: Oscar Zariski · 1966: John Milnor · 1967: Paul Cohen · 1968: Jerzy Neyman · 1969: William Feller
1970s

1970: Richard Brauer · 1973: John Tukey · 1974: Kurt Gödel · 1975: John W. Backus · Shiing-Shen Chern · George Dantzig · 1976: Kurt Otto Friedrichs · Hassler Whitney · 1979: Joseph Leo Doob · Donald E. Knuth
1980s

1982: Marshall Harvey Stone · 1983: Herman Goldstine · Isadore Singer · 1986: Peter Lax · Antoni Zygmund · 1987: Raoul Bott · Michael Freedman · 1988: Ralph E. Gomory · Joseph B. Keller · 1989: Samuel Karlin · Saunders MacLane · Donald C. Spencer
1990s

1990: George F. Carrier · Stephen Cole Kleene · John McCarthy · 1991: Alberto Calderón · 1992: Allen Newell · 1993: Martin David Kruskal · 1994: John Cocke · 1995: Louis Nirenberg · 1996: Richard Karp · Stephen Smale · 1997: Shing-Tung Yau · 1998: Cathleen Synge Morawetz · 1999: Felix Browder · Ronald R. Coifman
2000s

2000: John Griggs Thompson · Karen K. Uhlenbeck · 2001: Calyampudi R. Rao · Elias M. Stein · 2002: James G. Glimm · 2003: Carl R. de Boor · 2004: Dennis P. Sullivan · 2005: Bradley Efron · 2006: Hyman Bass · 2007: Leonard Kleinrock · Andrew J. Viterbi ·